#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<tools_rbtree.h>
#include<tools_avltree.h>
#include <tools/tools_int_map.h>
#include <tools_heap.h>
#include<time.h>
#include<map>
#include<tools/intrbtree.h>
#include<tools/doublerbtree.h>
#include<tools/inthashmap.h>
#include<tools_vector.h>
using namespace std;

int memery_leak_from_RB_Tree_compute;
int memery_leak_from_RB_Tree_compute_f;

void test_rb()
{
    RB_Tree*tree=(RB_Tree*)LB_MALLOC(sizeof(RB_Tree));
    rb_tree_init_int(tree);
    RB_int rbt,*rbt1;
    for(int i=0;i<99;i++)
    {
        rbt.key=i;
        tree->insert(tree,&rbt);
    }
   // print_self(tree);
    rbt.key=240;
    rbt1=(RB_int*)(tree->find(tree,&rbt));
    tree->insert(tree,&rbt);
   // print_self(tree);
    if(rbt1==NULL)
    {
        printf("dfsdfdn\n");
    }
    rb_tree_free(tree);

   /* RB_Tree* tree=(RB_Tree*)LB_malloc(sizeof(RB_Tree));
    RB_Tree_init(tree);
    tree->cmp=t_cmp;
    tree->copy=t_copy;
    rb_t t1;
    t1.key=3;
    tree->insert(tree,&t1);
    t1.key=2;
    tree->insert(tree,&t1);
    t1.key=-3;
    tree->insert(tree,&t1);
    t1.key=0;
    tree->insert(tree,&t1);
    t1.key=99;
    tree->insert(tree,&t1);
    t1.key=-82;
    tree->insert(tree,&t1);
    for(int i=0;i<34;i++)
    {
        t1.key=i;
        tree->insert(tree,&t1);
    }
    print_self(tree);
    t1.key=20;
    tree->erase(tree,&t1);
    t1.key=-100;
    tree->erase(tree,&t1);
    print_self(tree);*/
}
int cmp_int(void *a,void* b)
{
    int *a1=(int*)a,* b1=(int*)b;
    if(*a1==*b1)
    {
        return 0;
    }
    else if(*a1>*b1)
    {
        return 1;
    }
    else
    {
        return -1;
    }

}
void test_bub()
{
    Node* node=NULL;
    int * value=(int*)LB_MALLOC(sizeof(int));
    *value=8;

    node=node_overlying(node,value);
    value=(int*)LB_MALLOC(sizeof(int));
    *value=3;

    node=node_overlying(node,value);


    value=(int*)LB_MALLOC(sizeof(int));
    *value=5;
    node=node_overlying(node,value);

    value=(int*)LB_MALLOC(sizeof(int));
    *value=-1;

    node=node_overlying(node,value);

    for(Node* nit=node;nit!=NULL;nit=(Node*)(nit->Next))
    {
        printf("v:%d ",*((int*)(nit->value)));
    }
    printf("\n");
    node=node_bub_sortn(node,cmp_int);
    printf("end\n");
    for(Node* nit=node;nit!=NULL;nit=(Node*)(nit->Next))
    {
        printf("v:%d ",*((int*)(nit->value)));
    }
    printf("\n");



}

void test_rbtree()
{
    RB_INT_MAP rim;
    srand((unsigned)time(NULL));
    int  values[300];
    for(int i=0;i<300;i++)
    {
        values[i]=rand()%1000-500;
        printf("%d\n",values[i] );
        rim.insert(values[i],NULL);
    }
   rim.print_self();

    RB_int rbt;
    for(int i=0;i<300;i++)
    {
        //printf("her\n");
        rbt.key=values[i];
        //rim.tree->find(rim.tree,&rbt);

       rim.tree->erase(rim.tree,&rbt);
    }

    rim.print_self();
}
void test_avl()
{
    AVL_Tree tr;
    avl_tree_init_int(&tr);
    AVL_int  ai;
    //ai.key=0;
    //tr.insert(&tr,&ai);

    for(int i=0;i<300;i++)
    {
        ai.key=rand()%1000-500;
        tr.insert(&tr,&ai);
        //printf("%d\n",values[i] );
        //rim.insert(values[i],NULL);
    }
    printf("avl size:%d\n",tr.size );

}

void test_speed()
{
    clock_t t = clock();
    // std::map<int,void*> m;
    // for(int i=0;i<9999999;i++)
    // {
    //     m[rand()%100000]=NULL;
    // }
    // RB_INT_MAP rim;
    // for(int i=0;i<9999999;i++)
    // {
    //     rim.insert(rand()%100000,NULL);
    // }
    int num=0,num_i=0;
    for(int j=0;j<50;j++)
    {
        Int_RB_Tree *tr=(Int_RB_Tree*)LB_MALLOC(sizeof(Int_RB_Tree));
        int_rb_tree_init(tr);
        for(int i=0;i<799990;i++)
        {
            int_rb_tree_insert(tr,i,NULL);
            num_i++;
        }
        for(int i=0;i<999990;i++)
        {
            void*value=tr->find(tr,i);
            if(i==7000&&value==NULL)
            {
                num++;
                break;
            }
        }
        int_rb_tree_free(tr);
    }
    printf("num:%d\n",num);

    // int values[99999]={0};
    // for(int i=0;i<9999999;i++)
    // {
    //     if(i<99999)
    //     {
    //         values[i]=rand()%100000;

    //         int_rb_tree_insert(&tr,values[i],NULL);
    //     }
    //     else
    //     {
    //          int_rb_tree_insert(&tr,rand()%100000,NULL);
    //     }

    //  }
    // printf("%d\n",tr.size );
    // for(int i=0;i<99999;i++)
    // {
    //     int_rb_tree_delete_key(&tr,values[i]);
    // }



    printf("运行时间%.4f秒:%d\n", (double)(clock() - t) / CLOCKS_PER_SEC,0);
}
static inline int comp1(const void* v1,const void*v2)
{
    int * vv1=(int*)v1;
    int * vv2=(int*)v2;
    return ((*vv1)>(*vv2)?1:((*vv1)<(*vv2)?(-1):0));

}
void test_heap()
{
    CHeap *ch=(CHeap*)LB_MALLOC(sizeof(CHeap));
    cheap_init(ch);
    ch->values=(void**)LB_MALLOC(sizeof(void*)*50);ch->max_size=100;

    memset(ch->values,0,sizeof(void*)*50);


    for(int i=0;i<9;i++)
    {
        ch->values[i]=LB_MALLOC(sizeof(int));
    }
    *((int*)(ch->values[0]))=10;*((int*)(ch->values[1]) )=78;*((int*)(ch->values[2]) )=99;*((int*)(ch->values[3]) )=45;*((int*)(ch->values[4]))=67;
    *((int*)(ch->values[5]))=45;*((int*)(ch->values[6]))=0;*((int*)(ch->values[7]))=77;*((int*)(ch->values[8]))=34;

    ch->size=9;
    ch->comp=comp1;
    ch->mark=0;
    make_cheap(ch);
    int *vv=(int*)malloc(sizeof(int));
    *vv=66;
    insert_cheap(ch,vv);
    vv=(int*)malloc(sizeof(int));
    *vv=55;
    insert_cheap(ch,vv);
    vv=(int*)malloc(sizeof(int));
    *vv=25;
    insert_cheap(ch,vv);
    vv=(int*)malloc(sizeof(int));
    *vv=-5;
    insert_cheap(ch,vv);
    vv=(int*)malloc(sizeof(int));
    *vv=36;
    insert_cheap(ch,vv);

    for(int i=0;i<14;i++)
    {
        int *v=(int*)pop_cheap(ch);
        printf(" headp :%d\n",*v);
        free(v);
    }

}

static inline void DepthAndOffset(int idx, int& depth,int& offset)
{
   int i=idx+1;
   depth=-1;
   while(i){
      i>>=1;
      depth++;
   }
   offset=(idx+1)-(1<<depth);
}

int main(int argc,char**argv)
{

    int depth=-1,offset=-1;
    DepthAndOffset(0,depth,offset);
    printf("depth:%d offset:%d\n",depth,offset);

    memery_leak_from_RB_Tree_compute=0;
    memery_leak_from_RB_Tree_compute_f=0;
    RB_INT_MAP rim;
    rim.insert(-18,NULL);
    rim.insert(5,NULL);
    rim.insert(7,NULL);
    rim.insert(-9,NULL);
    rim.insert(0,NULL);
    rim.insert(-50,NULL);
    rim.insert(3,NULL);
    rim.insert(8,NULL);
    rim.insert(100,NULL);
    rim.insert(-100,NULL);
    rim.insert(50,NULL);
    rim.insert(26,NULL);
    rim.insert(75,NULL);
    rim.insert(35,NULL);
    rim.insert(80,NULL);
    rim.insert(20,NULL);
    rim.insert(90,NULL);
    rim.insert(-95,NULL);
    rim.insert(-36,NULL);
    rim.insert(-77,NULL);
    rim.insert(45,NULL);
    rim.insert(101,NULL);
    rim.insert(103,NULL);
    rim.insert(107,NULL);
    rim.insert(110,NULL);
    rim.insert(111,NULL);
    rim.insert(112,NULL);
    rim.insert(113,NULL);
    RB_int rbt;rbt.key=107;
    rim.tree->erase(rim.tree,&rbt);
    rbt.key=0;
    rim.tree->erase(rim.tree,&rbt);
    rbt.key=80;

    rim.tree->erase(rim.tree,&rbt);
            //printf("fdfdsfds\n") rim.tree->erase(rim.tree,&rbt);;

    rim.print_self();
    rim.find(113);
    rim.clear();

    Node* n1=NULL,*n2=NULL;
    Node* n3=node_union(n1,n2);
    n3=node_intersection(n1,n2);
    test_bub();

    //AVL_Tree * at=(AVL_Tree*)LB_MALLOC(sizeof(AVL_Tree));
    //avl_tree_init(at);

    //printf("fdsfdsfsdfffffffffffff\n");
    // AVL_Node* an1=(AVL_Node*)LB_MALLOC(sizeof(AVL_Node));
    // avl_node_init(an1);
    // if(NULL)
    // {
    //     printf("shi\n");
    // }
    // else
    // {
    //     printf("fdsfdsf\n");
    // }
   /// node_bub_sortn(Node* n,int (*cmp)(void* a,void* b));

   // rbt1=(RB_int*)(tree->find(tree,&rbt));
   // printf("find:%d\n",rbt1->key);
    /*printf("size:%d\n",tree->size);
    t1.key=30;
    tree->erase(tree,&t1);
    printf("size:%d\n",tree->size);*/
   //printf("size:%d\n",tree->size);
   // printf("%ld\n",tree->size);

  //  RB_Tree_free(tree);

    //RB_Tree_free(tree);
    test_rbtree();
    test_avl();
    //test_rb();
   // test_map();
    printf("begin test speed\n");
#if defined(_RB_USE_AUGMENTED_PTR)
    printf("kaiqi\n");
#endif
    test_speed();
    test_heap();
    int c;
    // fflush(stdin);

    // c = getchar();
    // while ((c = getchar()) != '\n' && c != EOF);
    // printf("%c\n",c);
    printf("end\nleak m :%d,leak f:%d\n",memery_leak_from_RB_Tree_compute,memery_leak_from_RB_Tree_compute_f);

    return 0;
}
